
#include <vector>
#include <stack>
#include <list>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;
//https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked
//https://github.com/fuxuemingzhu/Leetcode-Solution-All/blob/main/100-199/139.%20Word%20Break%20%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.md
//判断一个字符串能不能由给定的字典中的字符串拼接得到。
//单次拆分.cpp-139
//递归思路-回溯法解决

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(s.empty()||wordDict.empty()) return false;

        int n = s.size();
        unordered_set<string> st(wordDict.begin(),wordDict.end());
        vector<bool> dp(n,false);
    
        for(int i=0;i<n;++i){
            for(int j=0;j<=i;++j){
                if(j==0){
                    if (st.count(s.substr(j,i-j+1))) {
                        dp[i]=true;
                        break;
                    }
                }else if(dp[j-1]&& st.count(s.substr(j,i-j+1))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n-1];
    }
};

class Solution {
public:
    bool handle(string s, vector<string>& wordDict){
        for(auto substr :wordDict){
            auto loc=s.find(substr);
            if(loc!=0){
                continue;
            }
            if(substr.size()==s.size()){
                return true;
            }
            std::string tmp=s;
            tmp.erase(loc,substr.size());
            if(handle(tmp,wordDict)){
                return true;
            }
        }
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        if(s.empty()||wordDict.size()==0) return false;
        return handle(s,wordDict);
    }
};
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size(),false);
        for(size_t i=0;i<s.size();++i){
            for(auto w:wordDict){
                if(i+1<w.size()){
                    continue;
                }else if(w.size()==i+1){
                    if(w==s.substr(0,i+1)){
                         dp[i]=true;
                         break;
                    }
                }else{
                    string sub_str=s.substr(i-w.size()+1,w.size());
                    if(sub_str==w){
                        if(dp[i]=dp[i-w.size()]){
                            break;
                        }
                    }
                }
            }
        }
        return dp[s.size()-1];
    }   
};